package jps;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public abstract class JumpPointFinderBase {

    protected PriorityQueue<Node> openList;
    protected Node startNode;
    protected Node endNode;
    protected Grid grid;

    public JumpPointFinderBase(int startX, int startY, int endX, int endY, Grid grid) {
        this.grid = grid;
        this.openList = new PriorityQueue<>();
        this.startNode = grid.getNodeAt(startX, startY);
        this.endNode = grid.getNodeAt(endX, endY);
        // push the start node into the open list
        this.openList.add(this.startNode);
        this.startNode.setOpened(true);
    }

    public List<int[]> findPath() {
        // while the open list is not empty
        while (!this.openList.isEmpty()) {
            // pop the position of node which has the minimum `f` value.
            Node node = this.openList.poll();
            node.setClosed(true);
            if (node == this.endNode) {
                return this.compressPath(this.backtrace(node));
            }
            this.identifySuccessors(node);
        }
        // fail to find the path
        return null;
    }

    private void identifySuccessors(Node node) {
        int x = node.getX();
        int y = node.getY();
        List<int[]> neighbors = this.findNeighbors(node);
        for (int i = 0, l = neighbors.size(); i < l; ++i) {
            int[] neighbor = neighbors.get(i);
            int[] jumpPoint = this.jump(neighbor[0], neighbor[1], x, y);
            if (jumpPoint != null) {
                int jx = jumpPoint[0];
                int jy = jumpPoint[1];
                Node jumpNode = this.grid.getNodeAt(jx, jy);
                if (jumpNode.isClosed()) {
                    continue;
                }
                // include distance, as parent may not be immediately adjacent:
                int d = Util.octile(Math.abs(jx - x), Math.abs(jy - y));
                int ng = node.getG() + d; // next `g` value
                if (!jumpNode.isOpened() || ng < jumpNode.getG()) {
                    jumpNode.setG(ng);
                    if (jumpNode.getH() == 0) {
                        int endX = this.endNode.getX();
                        int endY = this.endNode.getY();
                        jumpNode.setH(Util.heuristic(Math.abs(jx - endX), Math.abs(jy - endY)));
                    }
                    jumpNode.setF(jumpNode.getG() + jumpNode.getH());
                    jumpNode.setParent(node);
                    if (!jumpNode.isOpened()) {
                        this.openList.add(jumpNode);
                        jumpNode.setOpened(true);
                    }
                }
            }
        }
    }

    private List<int[]> backtrace(Node node) {
        List<int[]> paths = new ArrayList<int[]>();
        paths.add(new int[] { node.getX(), node.getY() });
        while (node.getParent() != null) {
            node = node.getParent();
            paths.add(new int[] { node.getX(), node.getY() });
        }
        Collections.reverse(paths);
        return paths;
    }

    private List<int[]> compressPath(List<int[]> path) {
        if (path.size() < 3) {
            return path;
        }
        List<int[]> compressed = new ArrayList<>();
        int sx = path.get(0)[0]; // start x
        int sy = path.get(0)[1]; // start y
        int px = path.get(1)[0]; // second point x
        int py = path.get(1)[1]; // second point y
        int dx = px - sx; // direction between the two points
        int dy = py - sy; // direction between the two points
        int lx, ly;
        int ldx, ldy;
        int sq, i;
        sq = (int) Math.sqrt(dx * dx + dy * dy);
        dx /= sq;
        dy /= sq;
        compressed.add(new int[] { sx, sy });
        for (i = 2; i < path.size(); i++) {
            lx = px;
            ly = py;
            ldx = dx;
            ldy = dy;
            px = path.get(i)[0];
            py = path.get(i)[1];
            dx = px - lx;
            dy = py - ly;
            sq = (int) Math.sqrt(dx * dx + dy * dy);
            dx /= sq;
            dy /= sq;
            if (dx != ldx || dy != ldy) {
                compressed.add(new int[] { lx, ly });
            }
        }
        compressed.add(new int[] { px, py });
        return compressed;
    }

    protected abstract int[] jump(int i, int j, int x, int y);

    protected abstract List<int[]> findNeighbors(Node node);
}
